package com.huangyi;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        //数据流的中位数
        class MedianFinder {
            // left: 最大堆，装较小的一半；right: 最小堆，装较大的一半
            private PriorityQueue<Integer> left;
            private PriorityQueue<Integer> right;

            public MedianFinder() {
                left  = new PriorityQueue<>((a, b) -> Integer.compare(b, a)); // max-heap
                right = new PriorityQueue<>();                                 // min-heap
            }

            public void addNum(int num) {
                // 1) 先按与 left.peek() 的关系放入对应堆
                if (left.isEmpty() || num <= left.peek()) {
                    left.offer(num);
                } else {
                    right.offer(num);
                }

                // 2) 尺寸再平衡：left 只能比 right 多 1
                if (left.size() == right.size() + 2) {
                    right.offer(left.poll());
                } else if (right.size() == left.size() + 1) {
                    left.offer(right.poll());
                }
            }

            public double findMedian() {
                int total = left.size() + right.size();
                if ((total & 1) == 1) {           // 奇数：left 多一个
                    return left.peek();
                } else {                          // 偶数：两堆顶求平均
                    return ((long) left.peek() + (long) right.peek()) / 2.0;
                }
            }
        }



        //图像渲染
        class Solution {
            // 四个方向：右、左、下、上
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};

            public int[][] floodFill(int[][] image, int sr, int sc, int color) {
                int tmp = image[sr][sc];
                if (tmp == color) return image; // 避免死循环
                int m = image.length, n = image[0].length;

                Queue<int[]> q = new LinkedList<>();
                q.offer(new int[]{sr, sc});

                while (!q.isEmpty()) {
                    int[] num = q.poll();
                    int a = num[0], b = num[1];

                    image[a][b] = color; // 染色，相当于 visited

                    for (int i = 0; i < 4; i++) {
                        int x = a + dx[i], y = b + dy[i];
                        if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == tmp) {
                            q.offer(new int[]{x, y});
                        }
                    }
                }
                return image;
            }
        }

    }
}